# -*- coding: utf-8 -*-
# @Time    : 2024/6/13 15:31
# @Author  : yujiahao
# @File    : 21_function_recursion.py
# @description:Python中的递归


'''

【递归】说白了就是自己调自己

【递归要满足两个条件】
    1、不断的调用自己本身
    2、有明确的终止条件，这个很重要，不然无限递归，不仅本身不对，而且无终止的话可能一个代码把资源占完了，那就讨厌了。

【递归的优缺点】
    优点
        简洁性：递归可以使代码更加简洁和易读，特别是对于一些自然具有递归性质的问题。
        自然性：某些问题（如树的遍历、图的搜索）本身就是递归性质的，递归解法非常直观。
    缺点
        性能问题：递归可能会导致大量的函数调用，增加了时间和空间的复杂度。例如，计算斐波那契数列的递归方法效率低下，因为它会重复计算相同的子问题。
        栈溢出：递归深度过大时，会导致栈溢出错误。
【优化递归】

    1. 记忆化（Memoization）
    通过记忆化技术，可以避免重复计算相同的子问题，从而提高效率。

        def fibonacci_memo(n, memo={}):
            if n in memo:
                return memo[n]
            if n == 0:
                return 0
            elif n == 1:
                return 1
            else:
                memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
                return memo[n]

        print(fibonacci_memo(50))  # 输出 12586269025

    2. 尾递归优化（Tail Recursion）
        某些语言（如Scheme）支持尾递归优化，可以将尾递归转换为迭代，从而避免栈溢出。
        然而，Python不支持尾递归优化，因此在Python中使用尾递归并不能减少栈的深度。

【总结】

    递归是解决某些问题的强大工具，但需要小心使用。理解递归的基本原理和潜在问题，以及如何优化递归算法，对于编写高效的递归代码至关重要。通过记忆化技术和理解递归的本质，可以有效地避免性能问题和栈溢出错误。
'''

# 这就是一个很简单的递归
def func(n):
    """
    打印从 n 到 1 的所有整数
    :param n: 整数 n
    """
    # 递归结束条件
    if n == 0:
        return
    # 打印当前的 n
    print(n)
    # 递归调用，参数为 n-1
    func(n - 1)

# 调用函数，打印 5 到 1 的整数
func(5)

print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')



# 遍历这个列表的个元素，包括子列表的元素


lst_s = [1, 3, 4, "alex", [3, 7, 8, "TaiBai"], 5, "RiTiAn"]
lst_l = [1, 3, 4, "alex", [3, 7, 8, "jfag"], 5, "fjeiwaojp",[4,5,6,[7,[11,12,34,["jewqipfe","vq","gwqfeqwkgrqg"],5],10,8,9]]]



# 发现列表有嵌套，看lst_s套了2层用for循环还可以打印，如果100层呢就不好弄了
for i in lst_s:

    if isinstance(i, list):
        for j in i:
            print(j)
    else:
        print(i)


print('''\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n''')

# 使用递归的方式遍历一下lst_l,就方便多了
def  ff(lst):

    if isinstance(lst, list):
        for j in lst:
            ff(j)
    else:
        print(lst)

ff(lst_l)






print('''\n-----------------------------------☆☆☆经典练习☆☆☆----------------------------------------\n''')


# 1. 计算阶乘
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

# 示例
print(f'计算5的阶乘：{factorial(5)}')  # 输出 120

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 2. 斐波那契数列
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 示例
print(f'计算第10个斐波那契数：{fibonacci(10)}')  # 输出 55

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 3. 递归遍历嵌套列表
def print_nested_list(lst):
    for item in lst:
        if isinstance(item, list):
            print_nested_list(item)
        else:
            print(item)

# 示例
nested_list = [1, [2, 3, [4, 5]], 6, [7, 8], "hello"]
print('递归遍历嵌套列表：')
print_nested_list(nested_list)

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 4. 二分查找
def binary_search(arr, target, low, high):
    if low > high:
        return -1  # 未找到目标
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, high)

# 示例
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
print(f'在数组 {arr} 中查找数字 {target} 的索引：{binary_search(arr, target, 0, len(arr) - 1)}')  # 输出 4

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 5. 汉诺塔问题
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)

# 示例
print('汉诺塔问题解决方案：')
hanoi(3, 'A', 'C', 'B')

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 6. 计算字符串的全排列
def permute(s, l, r):
    if l == r:
        print(''.join(s))
    else:
        for i in range(l, r + 1):
            s[l], s[i] = s[i], s[l]  # 交换
            permute(s, l + 1, r)
            s[l], s[i] = s[i], s[l]  # 回溯

# 示例
print('字符串 "ABC" 的所有全排列：')
s = list("ABC")
permute(s, 0, len(s) - 1)

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 7. 反转字符串
def reverse_string(s):
    if len(s) == 0:
        return s
    else:
        return reverse_string(s[1:]) + s[0]

# 示例
print(f'反转字符串 "hello"：{reverse_string("hello")}')  # 输出 "olleh"

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 8. 求最大公约数（GCD）
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 示例
print(f'计算 48 和 18 的最大公约数：{gcd(48, 18)}')  # 输出 6

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 9. 计算数字的幂
def power(x, n):
    if n == 0:
        return 1
    else:
        return x * power(x, n - 1)

# 示例
print(f'计算 2 的 3 次幂：{power(2, 3)}')  # 输出 8

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 10. 迷宫求解
def solve_maze(maze, x, y, solution):
    if x == len(maze) - 1 and y == len(maze[0]) - 1:
        solution[x][y] = 1
        return True
    if x >= 0 and x < len(maze) and y >= 0 and y < len(maze[0]) and maze[x][y] == 1:
        solution[x][y] = 1
        if solve_maze(maze, x + 1, y, solution):
            return True
        if solve_maze(maze, x, y + 1, solution):
            return True
        solution[x][y] = 0
        return False
    return False

# 示例迷宫
maze = [
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 1]
]
solution = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]

print('迷宫求解方案：')
if solve_maze(maze, 0, 0, solution):
    for row in solution:
        print(row)
else:
    print("No solution")

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 11. 生成所有括号组合
def generate_parentheses(n):
    def backtrack(s='', left=0, right=0):
        if len(s) == 2 * n:
            result.append(s)
            return
        if left < n:
            backtrack(s + '(', left + 1, right)
        if right < left:
            backtrack(s + ')', left, right + 1)

    result = []
    backtrack()
    return result

# 示例
print(f'生成所有可能的括号组合（n=3）：{generate_parentheses(3)}')  # 输出 ["((()))", "(()())", "(())()", "()(())", "()()()"]

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 12. 计算数组元素的和
def sum_array(arr):
    if len(arr) == 0:
        return 0
    else:
        return arr[0] + sum_array(arr[1:])

# 示例
print(f'计算数组 [1, 2, 3, 4, 5] 的元素和：{sum_array([1, 2, 3, 4, 5])}')  # 输出 15

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 13. 计算字符串长度
def string_length(s):
    if s == '':
        return 0
    else:
        return 1 + string_length(s[1:])

# 示例
print(f'计算字符串 "hello" 的长度：{string_length("hello")}')  # 输出 5

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 14. 计算数列的和
def sum_series(n):
    if n == 0:
        return 0
    else:
        return n + sum_series(n - 1)

# 示例
print(f'计算数列 1 + 2 + 3 + ... + 5 的和：{sum_series(5)}')  # 输出 15

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 15. 合并两个有序链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_two_lists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = merge_two_lists(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists(l1, l2.next)
        return l2

# 示例
# 创建链表 1->2->4 和 1->3->4
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))
merged_list = merge_two_lists(l1, l2)

# 打印合并后的链表
print('合并两个有序链表后的结果：', end="")
while merged_list:
    print(merged_list.val, end=" ")
    merged_list = merged_list.next
# 输出 1 1 2 3 4 4

print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 16. 全排列（Permutations）
def permute(nums):
    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]

    result = []
    backtrack(0)
    return result

# 示例
print(f'数组 [1, 2, 3] 的所有全排列：{permute([1, 2, 3])}')  # 输出 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]




print('\n-----------------------------------☆☆☆分割线☆☆☆----------------------------------------\n')


# 17. 使用记忆化递归优化爬楼梯问题
def climb_stairs_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
        return memo[n]

# 示例
n = 5
print(f'爬 {n} 阶楼梯的方法总数（使用记忆化递归）：{climb_stairs_memo(n)}')  # 输出 8
